#include <iostream>
#include <vector>

using namespace std;

/// @brief 仿函数
/// @tparam T
template <class T>
struct _HashFunc {
  size_t operator()(const T& key) { return key; }
};

/// @brief string类型特化
/// @brief string需要对其每一个字符计算hash
template <>
struct _HashFunc<string> {
  size_t operator()(const string& key) {
    size_t hash = 0;
    for (auto c : key) {
      hash = hash * 131 + c;
    }
    return hash;
  }
};

/// @brief 哈希结点状态
enum HASH_STATE { HASH_EMPTY, HASH_DELETED, HASH_USED };

/// @brief 素数表
/// @brief 表内为哈希表扩充容量 (素数除了一和它本身就没有其他因数，降低哈希冲突)
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] = {
    53ul,         97ul,         193ul,       389ul,       769ul,
    1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
    49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
    1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
    50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
    1610612741ul, 3221225473ul, 4294967291ul};

/// @brief 哈希结点
/// @tparam K 键类型
/// @tparam V 值类型
template <class K, class V>
struct HashTableNode {
  K _key;
  V _value;
  HASH_STATE _state;  // 结点状态
  HashTableNode(const K& key = K(), const V& value = V(),
                HASH_STATE state = HASH_EMPTY)
      : _key(key), _value(value), _state(state) {}
};

/// @brief 哈希表
/// @tparam K 键类型
/// @tparam V 值类型
/// @tparam HashFunc
template <class K, class V, class HashFunc = _HashFunc<K>>
class HashTable {
  typedef HashTableNode<K, V> Node;

 public:
  HashTable() = default;
  HashTable(size_t size) : _size(0) { _table.resize(size); }

  /// @brief 散列函数
  /// @param key 键
  /// @return 哈希值
  ssize_t _HashTableFunc(const K& key) {
    HashFunc hash;
    ssize_t hash_value = hash(key);
    // 除留余数法
    return hash_value % _table.size();
  }

  /// @brief 插入元素
  /// @param key 键
  /// @param value 值
  /// @return 插入的结点
  pair<Node*, bool> Insert(const K& key, const V& value) {
    // 检查容量
    checkCapacity();
    // 获取哈希值
    ssize_t index = _HashTableFunc(key);
    // 使用线性探测法寻找空位并插入
    while (_table[index]._state != HASH_EMPTY) {
      index++;
      // 从头寻找
      if (index == _table.size()) index = 0;
    }
    _table[index]._key = key;
    _table[index]._value = value;
    _table[index]._state = HASH_USED;
    _size++;
    return make_pair<Node*, bool>(&_table[index], true);
  }

  /// @brief 删除结点
  /// @param key 键
  void Delete(const K& key) {
    Node* delNode = Find(key);
    if (delNode) delNode->_state = HASH_DELETED;
  }

  /// @brief 寻找结点
  /// @param key 键
  /// @return 查找到的结点
  Node* Find(const K& key) {
    ssize_t index = _HashTableFunc(key);
    // 使用线性探测法查找
    while (_table[index]._state == HASH_USED) {
      if (_table[index]._key == key) {
        return &_table[index];
      }
      index++;
      if (index == _size) index = 0;
    }
    return NULL;
  }

  void Show() const {
    for (int i = 0; i < _size; ++i) {
      cout << "[" << i + 1 << "] " << _table[i]._key << " -> " << _table[i]._value << endl;
    }
  }

 private:
  /// @brief 替换底层容器
  /// @param other
  void swap(HashTable& other) {
    std::swap(_table, other._table);
    std::swap(_size, other._size);
  }

  /// @brief 容量检查
  void checkCapacity() {
    // 若为空扩容到11
    if (_table.empty()) _table.resize(11);
    // 超过比例系数则进行扩容 (已有元素个数 / 容器大小 > 0.75)
    if (_size * 10 / _table.size() >= 7) {
      size_t index = 0;
      // 寻找素数表中扩充容量与当前容量近似值
      while (_PrimeList[index++] < _table.size()) {
      }
      ssize_t new_size = _PrimeList[index];
      // 创建相应素数大小新表
      HashTable<K, V> newHT(new_size);
      // 复制元素到新表 (重新散列)
      for (ssize_t i = 0; i < _table.size(); ++i) {
        if (_table[i]._state == HASH_USED)
          newHT.Insert(_table[i]._key, _table[i]._value);
      }
      swap(newHT);
    }
  }

 private:
  vector<Node> _table;
  size_t _size;
};

int main(int argc, char const* argv[]) {
  int arr[]{3, 7, 12, 23, 45, 67, 13, 43};
  HashTable<int, int> ht;
  for (int i = 0; i < 8; ++i) ht.Insert(arr[i], arr[i] + 3);
  ht.Show();
  return 0;
}
